package leetcode.editor.cn;

import arithmetic.A_01_ReverseHead;
import arithmetic2.ListNode;

//[206]反转链表

/**
 * @see  A_01_ReverseHead
 */
public class ReverseLinkedList206{
public static void main(String[] args) {
   Solution solution = new ReverseLinkedList206().new Solution();
   
}

  //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //for ...
//        ListNode pri = null;
//        ListNode current = head;
//        while (current != null ){
//            ListNode next = current.next;//cache next
//            current.next = pri;//反转
//            pri = current; //cache
//            current = next; //遍历的节点, 最后是null
//        }
//        return pri;

        //递归
        //stop
        if (head==null || head.next==null){
            return head;//最后的节点。
        }
        //下一个节点
        ListNode next = head.next;
        //递归到终点
        ListNode lastNode = reverseList(next);
        //反转下一个节点
        ListNode next2 = next.next;
        next.next = head;
        //反转当前，
        head.next = null;
        return lastNode;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}